package com.leetcode.array;

import java.util.Arrays;

public class D_jobScheduing_fast {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        // 思路  先将三个值一起存入 jobs类中  再按照end进行排序
        int n = startTime.length;
        Jobs[] jobs = new Jobs[n];
        for (int i = 0; i < n; i++) {
            jobs[i] = new Jobs();
            jobs[i].s = startTime[i];
            jobs[i].e = endTime[i];
            jobs[i].p = profit[i];
        }

        // 排序
        Arrays.sort(jobs, (j1, j2) -> (int) j1.e - j2.e);

        // 动态规划
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = jobs[i].p;

        for (int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], jobs[i].p);

            for (int j = i - 1; j >= 0; j--) {
                if (jobs[j].e <= jobs[i].s) {
                    dp[i] = Math.max(dp[i], dp[j] + jobs[i].p);
                    break;
                }
            }
        }

        return dp[n - 1];
    }
}

class Jobs {
    int s, e, p;

    public Jobs(int s, int e, int p) {
        this.s = s;
        this.e = e;
        this.p = p;
    }

    public Jobs() {

    }

}
